#define _CRT_SECURE_NO_WARNINGS 1
/*
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
*/
#include <stdio.h>
#include <stdlib.h>
//时间复杂度为O(N^2),空间复杂度为O(1)
void rotate1(int* nums, int numsSize, int k)
{
	while (k--)
	{
		//创建新的变量来保存最后一个值
		int tmp = *(nums + numsSize - 1);
		//整体后移
		for (int i = numsSize; i > 0; i--)
		{
			*(nums + i - 1) = *(nums + i - 2);
		}
		//将保留的值赋给数组首元素
		*nums = tmp;
	}
}

//时间复杂度为O(N),空间复杂度为O(N)
void rotate2(int* nums, int numsSize, int k)
{
	//创建新的数组
	int* newnums = (int*)malloc(numsSize*sizeof(int));
	if (newnums == NULL)
	{
		perror("malloc fail!");
		return;
	}
	for (int i = 0; i < numsSize; i++)
	{
		*(newnums + (k + i) % numsSize) = *(nums + i);
	}
	//赋值给nums数组
	for (int i = 0; i < numsSize; i++)
	{
		*(nums + i) = *(newnums + i);
	}
}

//时间复杂度为O(N),空间复杂度为O(1)
void reveres(int* nums, int left, int right)
{
	while (left < right)
	{
		int tmp = *(nums + left);
		*(nums + left) = *(nums + right);
		*(nums + right) = tmp;
		left++;
		right--;
	}
}

void rotate(int* nums, int numsSize, int k)
{
	//处理k
	k %= numsSize;
	//逆置前n-k个数据
	reveres(nums, 0, numsSize - k - 1);
	//逆置后k个数据
	reveres(nums, numsSize - k, numsSize - 1);
	//整体逆置
	reveres(nums, 0, numsSize - 1);
}
int main()
{
	int arr[7] = { 1,2,3,4,5,6,7 };
	int sz = sizeof(arr) / sizeof(*(arr));
	rotate(arr, sz, 3);
	for (int i = 0; i < sz; i++)
		printf("%d ", *(arr + i));
	return 0;
}